{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum of Absolute Value Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxAbsValExpr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #绝对值表达式的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个长度相等的整数数组，返回下面表达式的最大值：</p>\n",
    "\n",
    "<p><code>|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|</code></p>\n",
    "\n",
    "<p>其中下标 <code>i</code>，<code>j</code> 满足&nbsp;<code>0 &lt;= i, j &lt; arr1.length</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [1,2,3,4], arr2 = [-1,4,5,6]\n",
    "<strong>输出：</strong>13\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]\n",
    "<strong>输出：</strong>20</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= arr1.length == arr2.length &lt;= 40000</code></li>\n",
    "\t<li><code>-10^6 &lt;= arr1[i], arr2[i] &lt;= 10^6</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-of-absolute-value-expression](https://leetcode.cn/problems/maximum-of-absolute-value-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-of-absolute-value-expression](https://leetcode.cn/problems/maximum-of-absolute-value-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n[-1,4,5,6]', '[1,-2,-5,0,10]\\n[0,-2,-1,-7,-4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, a: List[int], b: List[int]) -> int:\n",
    "        n = len(a)\n",
    "        \n",
    "        v = float('-inf')\n",
    "\n",
    "        max_1 = float('-inf')\n",
    "        max_2 = float('-inf')\n",
    "        max_3 = float('-inf')\n",
    "        max_4 = float('-inf')\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ci = a[i] + b[i]\n",
    "            di = a[i] - b[i]\n",
    "\n",
    "            max_1 = max(max_1, -ci + i)\n",
    "            max_2 = max(max_2, -di + i)\n",
    "            max_3 = max(max_3, di + i)\n",
    "            max_4 = max(max_4, ci + i)\n",
    "\n",
    "            v = max(v, -i + max(ci + max_1, di + max_2, -di + max_3, -ci + max_4))\n",
    "\n",
    "        return v\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = 0\n",
    "        # 枚举四个方向\n",
    "        for dx, dy in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:\n",
    "            maxv = -10000007\n",
    "            minv = 4000000\n",
    "            # 计算当前方向上的曼哈顿距离最小值和最大值\n",
    "            for i in range(n):\n",
    "                maxv = max(maxv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "                minv = min(minv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "            # 更新答案\n",
    "            ans = max(ans, maxv - minv)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = float('-inf')\n",
    "        for mask in range(8):\n",
    "            mx, mi = float('-inf'), float('inf')\n",
    "            A = [2 * (mask >> i & 1) - 1 for i in range(3)]\n",
    "            for B in zip(arr1, arr2, range(n)):\n",
    "                curr = sum(a * b for a, b in zip(A, B))\n",
    "                mx = max(mx, curr)\n",
    "                mi = min(mi, curr)\n",
    "            ans = max(ans, mx - mi)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        minA = minB = minC = minD = float('inf')\n",
    "        maxA = maxB = maxC = maxD = float('-inf')\n",
    "        for i in range(len(arr1)):\n",
    "            minA = min(minA, arr1[i] + arr2[i] + i)\n",
    "            maxA = max(maxA, arr1[i] + arr2[i] + i)\n",
    "            minB = min(minB, arr1[i] - arr2[i] + i)\n",
    "            maxB = max(maxB, arr1[i] - arr2[i] + i)\n",
    "            minC = min(minC, arr1[i] + arr2[i] - i)\n",
    "            maxC = max(maxC, arr1[i] + arr2[i] - i)\n",
    "            minD = min(minD, arr1[i] - arr2[i] - i)\n",
    "            maxD = max(maxD, arr1[i] - arr2[i] - i)\n",
    "        return max(maxA - minA, maxB - minB, maxC - minC, maxD - minD)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = 0\n",
    "        # 枚举四个方向\n",
    "        for dx, dy in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:\n",
    "            maxv = -inf\n",
    "            minv = inf\n",
    "            # 计算当前方向上的曼哈顿距离最小值和最大值\n",
    "            for i in range(n):\n",
    "                maxv = max(maxv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "                minv = min(minv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "            # 更新答案\n",
    "            ans = max(ans, maxv - minv)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "\n",
    "        ans = float('-inf')\n",
    "\n",
    "        min_ = arr1[0] + arr2[0]\n",
    "        for i in range(1, len(arr1)):\n",
    "            ans = max(ans, arr1[i] + arr2[i] + i - min_)\n",
    "            min_ = min(min_, arr1[i] + arr2[i] + i)\n",
    "\n",
    "        \n",
    "        min_ = arr1[0] - arr2[0]\n",
    "        for i in range(1, len(arr1)):\n",
    "            ans = max(ans, arr1[i] - arr2[i] + i - min_)\n",
    "            min_ = min(min_, arr1[i] - arr2[i] + i)\n",
    "        \n",
    "\n",
    "        min_ = -arr1[0] + arr2[0]\n",
    "        for i in range(1, len(arr1)):\n",
    "            ans = max(ans, -arr1[i] + arr2[i] + i - min_)\n",
    "            min_ = min(min_, -arr1[i] + arr2[i] + i)\n",
    "\n",
    "        min_ = -arr1[0] - arr2[0]\n",
    "        for i in range(1, len(arr1)):\n",
    "            ans = max(ans, -arr1[i] - arr2[i] + i - min_)\n",
    "            min_ = min(min_, -arr1[i] - arr2[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = 0\n",
    "        # 枚举四个方向\n",
    "        for dx, dy in [(1, 1), (-1, 1), (1, -1), (-1, -1)]:\n",
    "            maxv = -inf\n",
    "            minv = 4000000\n",
    "            # 计算当前方向上的曼哈顿距离最小值和最大值\n",
    "            for i in range(n):\n",
    "                maxv = max(maxv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "                minv = min(minv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "            # 更新答案\n",
    "            ans = max(ans, maxv - minv)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        def work(p1, p2):\n",
    "            mn = inf\n",
    "            ans = 0\n",
    "            for i, (x, y) in enumerate(zip(arr1, arr2)):\n",
    "                t = p1 * x + p2 * y + i\n",
    "                #print(t, mn)\n",
    "                ans = max(ans, t - mn)\n",
    "                mn = min(mn, t)\n",
    "            return ans\n",
    "        return max(work(1, 1), work(1, -1), work(-1, 1), work(-1, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        #2的3次方有8种情况，4种类型\n",
    "        n = len(arr1)\n",
    "        A_min = B_min = C_min = D_min = float('inf')\n",
    "        A_max = B_max = C_max = D_max = float('-inf')\n",
    "\n",
    "        for i in range(n):\n",
    "            A_min = min(A_min, arr1[i] + arr2[i] + i)\n",
    "            A_max = max(A_max, arr1[i] + arr2[i] + i)\n",
    "\n",
    "            B_min = min(B_min, arr1[i] + arr2[i] - i)\n",
    "            B_max = max(B_max, arr1[i] + arr2[i] - i)\n",
    "\n",
    "            C_min = min(C_min, arr1[i] - arr2[i] + i)\n",
    "            C_max = max(C_max, arr1[i] - arr2[i] + i)\n",
    "\n",
    "            D_min = min(D_min, arr1[i] - arr2[i] - i)\n",
    "            D_max = max(D_max, arr1[i] - arr2[i] - i)\n",
    "        \n",
    "        return max(A_max - A_min, B_max - B_min, C_max - C_min, D_max - D_min)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        def gr(f1, f2):\n",
    "            a = b = arr1[0] + f1 * arr2[0]\n",
    "            for i in range(len(arr1)):\n",
    "                v = arr1[i] + f1 * arr2[i] + f2 * i\n",
    "                if v < a:\n",
    "                    a = v\n",
    "                if v > b:\n",
    "                    b = v\n",
    "            return b - a\n",
    "        return max(gr(-1, -1), gr(-1, 1), gr(1, -1), gr(1, 1))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        amin, bmin, cmin, dmin = inf, inf, inf, inf\n",
    "        amax, bmax, cmax, dmax = -inf, -inf, -inf, -inf\n",
    "        for i in range(n):\n",
    "            amin = min(amin, arr1[i] + arr2[i] + i)\n",
    "            amax = max(amax, arr1[i] + arr2[i] + i)\n",
    "            bmin = min(bmin, arr1[i] - arr2[i] + i)\n",
    "            bmax = max(bmax, arr1[i] - arr2[i] + i)\n",
    "            cmin = min(cmin, -arr1[i] + arr2[i] + i)\n",
    "            cmax = max(cmax, -arr1[i] + arr2[i] + i)\n",
    "            dmin = min(dmin, -arr1[i] - arr2[i] + i)\n",
    "            dmax = max(dmax, -arr1[i] - arr2[i] + i)\n",
    "        return max(amax - amin, bmax - bmin, cmax - cmin, dmax - dmin)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        _max = -inf\n",
    "        n = len(arr1)\n",
    "        for dx, dy in [(1, 1), (1, -1), (-1, 1), (-1, -1)]:\n",
    "            _maxv = -inf\n",
    "            _minv = inf\n",
    "            for i in range(n):\n",
    "                t = arr1[i] * dx + arr2[i] * dy + i\n",
    "                _maxv = max(_maxv, t)\n",
    "                _minv = min(_minv, t)\n",
    "            _max = max(_maxv - _minv, _max)\n",
    "        return _max\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = float('-inf')\n",
    "        for mask in range(8):\n",
    "            mx, mi = float('-inf'), float('inf')\n",
    "            A = [2 * (mask >> i & 1) - 1 for i in range(3)]\n",
    "            for B in zip(arr1, arr2, range(n)):\n",
    "                curr = sum(a * b for a, b in zip(A, B))\n",
    "                mx = max(mx, curr)\n",
    "                mi = min(mi, curr)\n",
    "            ans = max(ans, mx - mi)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = 0\n",
    "        for x in [1, -1]:\n",
    "            for y in [1, -1]:\n",
    "                for z in [1, -1]:\n",
    "                    a1 = max(x*arr1[i]+y*arr2[i]+z*i for i in range(n))\n",
    "                    a2 = min(x*arr1[i]+y*arr2[i]+z*i for i in range(n))\n",
    "                    if a1 - a2 > ans:\n",
    "                        ans = a1 - a2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MIN = -10**6\n",
    "MAX = 10**6\n",
    "\n",
    "class Solution(object):\n",
    "    def maxAbsValExpr(self, arr1, arr2):\n",
    "        \"\"\"\n",
    "        :type arr1: List[int]\n",
    "        :type arr2: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        Aa, Ba, Ca, Da= MIN, MIN, MIN, MIN\n",
    "        Ab, Bb, Cb, Db= MAX, MAX, MAX, MAX\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A = x + y + i\n",
    "            B = x + y - i\n",
    "            C = x - y + i\n",
    "            D = x - y - i\n",
    "            Aa = max(Aa, A)\n",
    "            Ab = min(Ab, A)\n",
    "            Ba = max(Ba, B)\n",
    "            Bb = min(Bb, B)\n",
    "            Ca = max(Ca, C)\n",
    "            Cb = min(Cb, C)\n",
    "            Da = max(Da, D)\n",
    "            Db = min(Db, D)\n",
    "            \n",
    "        a = Aa - Ab\n",
    "        b = Ba - Bb\n",
    "        c = Ca - Cb\n",
    "        d = Da - Db\n",
    "        return max(a, b, c, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        res=-inf\n",
    "        mi=[inf]*4\n",
    "        mx=[-inf]*4\n",
    "        mina=minb=minc=mind=inf\n",
    "        maxa=maxb=maxc=maxd=-inf\n",
    "        for i in range(len(arr1)):\n",
    "            x,y,z=i,arr1[i],arr2[i]\n",
    "            arr=[x+y+z,x+y-z,x-y+z,x-y-z]\n",
    "            if i>0:\n",
    "                for j in range(4):\n",
    "                    res=max(res,abs(arr[j]-mi[j]),abs(arr[j]-mx[j]))\n",
    "            for i in range(4):\n",
    "                mi[i]=min(mi[i],arr[i])\n",
    "                mx[i]=max(mx[i],arr[i])          \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "max_ = lambda a, b: a if a >= b else b\n",
    "min_ = lambda a, b: a if a <= b else b\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        mxpp = mxpm = mxmp = mxmm = -inf\n",
    "        mnpp = mnpm = mnmp = mnmm = inf\n",
    "        for i, (x, y) in enumerate(zip(arr1, arr2)):\n",
    "            pp = x + y + i\n",
    "            mxpp = max_(mxpp, pp)\n",
    "            mnpp = min_(mnpp, pp)\n",
    "            pm = x + y - i\n",
    "            mxpm = max_(mxpm, pm)\n",
    "            mnpm = min_(mnpm, pm)\n",
    "            mp = x - y + i\n",
    "            mxmp = max_(mxmp, mp)\n",
    "            mnmp = min_(mnmp, mp)\n",
    "            mm = x - y - i\n",
    "            mxmm = max_(mxmm, mm)\n",
    "            mnmm = min_(mnmm, mm)\n",
    "        return max(mxpp-mnpp, mxpm-mnpm, mxmp-mnmp, mxmm-mnmm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = max(arr1[i]+arr2[i]+i for i in range(0, len(arr1))) - min(arr1[i]+arr2[i]+i for i in range(0, len(arr1)))\n",
    "        b = max(arr1[i]+arr2[i]-i for i in range(0, len(arr1))) - min(arr1[i]+arr2[i]-i for i in range(0, len(arr1)))\n",
    "        c = max(arr1[i]-arr2[i]-i for i in range(0, len(arr1))) - min(arr1[i]-arr2[i]-i for i in range(0, len(arr1)))\n",
    "        d = max(arr1[i]-arr2[i]+i for i in range(0, len(arr1))) - min(arr1[i]-arr2[i]+i for i in range(0, len(arr1)))\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a1 = max(arr1[i]+arr2[i]+i for i in range(0, len(arr1))) \n",
    "        a2 = min(arr1[i]+arr2[i]+i for i in range(0, len(arr1)))\n",
    "        a = a1 - a2\n",
    "        b1 = max(arr1[i]+arr2[i]-i for i in range(0, len(arr1))) \n",
    "        b2 = min(arr1[i]+arr2[i]-i for i in range(0, len(arr1)))\n",
    "        b = b1 - b2\n",
    "        c1 = max(arr1[i]-arr2[i]-i for i in range(0, len(arr1))) \n",
    "        c2 = min(arr1[i]-arr2[i]-i for i in range(0, len(arr1)))\n",
    "        c = c1 - c2\n",
    "        d1 = max(arr1[i]-arr2[i]+i for i in range(0, len(arr1))) \n",
    "        d2 = min(arr1[i]-arr2[i]+i for i in range(0, len(arr1)))\n",
    "        d = d1 - d2\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        mxpp = mxpm = mxmp = mxmm = -1 << 30\n",
    "        mnpp = mnpm = mnmp = mnmm = 1 << 30\n",
    "        for i, (x, y) in enumerate(zip(arr1, arr2)):\n",
    "            pp = x + y + i\n",
    "            mxpp = max(mxpp, pp)\n",
    "            mnpp = min(mnpp, pp)\n",
    "            pm = x + y - i\n",
    "            mxpm = max(mxpm, pm)\n",
    "            mnpm = min(mnpm, pm)\n",
    "            mp = x - y + i\n",
    "            mxmp = max(mxmp, mp)\n",
    "            mnmp = min(mnmp, mp)\n",
    "            mm = x - y - i\n",
    "            mxmm = max(mxmm, mm)\n",
    "            mnmm = min(mnmm, mm)\n",
    "        return max(mxpp-mnpp, mxpm-mnpm, mxmp-mnmp, mxmm-mnmm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a = max(arr1[i]+arr2[i]+i for i in range(0, len(arr1))) - min(arr1[i]+arr2[i]+i for i in range(0, len(arr1)))\n",
    "        b = max(arr1[i]+arr2[i]-i for i in range(0, len(arr1))) - min(arr1[i]+arr2[i]-i for i in range(0, len(arr1)))\n",
    "        c = max(arr1[i]-arr2[i]-i for i in range(0, len(arr1))) - min(arr1[i]-arr2[i]-i for i in range(0, len(arr1)))\n",
    "        d = max(arr1[i]-arr2[i]+i for i in range(0, len(arr1))) - min(arr1[i]-arr2[i]+i for i in range(0, len(arr1)))\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, a: List[int], b: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        res=0\n",
    "        for dx in [1,-1]:\n",
    "            for dy in [1,-1]:\n",
    "                for dz in [1,-1]:\n",
    "                    mi=inf\n",
    "                    mx=-inf\n",
    "                    for z,(x,y) in enumerate(zip(a,b)):\n",
    "                        mx=max(mx,x*dx+y*dy+z*dz)\n",
    "                        mi=min(mi,x*dx+y*dy+z*dz)\n",
    "                    res=max(res,mx-mi)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, a: List[int], b: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        res=0\n",
    "        for dx in [1,-1]:\n",
    "            for dy in [1,-1]:\n",
    "                mi=inf\n",
    "                mx=-inf\n",
    "                for i,(x,y) in enumerate(zip(a,b)):\n",
    "                    mx=max(mx,x*dx+y*dy+i)\n",
    "                    mi=min(mi,x*dx+y*dy+i)\n",
    "                res=max(res,mx-mi)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n = len(arr1)\n",
    "        ans = 0\n",
    "\n",
    "        for dx, dy in[(1, 1), (-1, 1), (1, -1), (-1, -1)]:\n",
    "            maxv = -400000\n",
    "            minv = 400000\n",
    "            for i in range(n):\n",
    "                maxv = max(maxv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "                minv = min(minv, arr1[i] * dx + arr2[i] * dy + i)\n",
    "            ans = max(ans, maxv - minv)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        a1 = max(arr1[i]+arr2[i]+i for i in range(0, len(arr1))) \n",
    "        a2 = min(arr1[i]+arr2[i]+i for i in range(0, len(arr1)))\n",
    "        a = a1 - a2\n",
    "        b1 = max(arr1[i]+arr2[i]-i for i in range(0, len(arr1))) \n",
    "        b2 = min(arr1[i]+arr2[i]-i for i in range(0, len(arr1)))\n",
    "        b = b1 - b2\n",
    "        c1 = max(arr1[i]-arr2[i]-i for i in range(0, len(arr1))) \n",
    "        c2 = min(arr1[i]-arr2[i]-i for i in range(0, len(arr1)))\n",
    "        c = c1 - c2\n",
    "        d1 = max(arr1[i]-arr2[i]+i for i in range(0, len(arr1))) \n",
    "        d2 = min(arr1[i]-arr2[i]+i for i in range(0, len(arr1)))\n",
    "        d = d1 - d2\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        len_arr = len(arr1)\n",
    "        ppp = [arr1[i]+arr2[i]+i for i in range(len_arr)]\n",
    "        a1 = (max(ppp)-min(ppp))\n",
    "        ppp = [arr1[i]+arr2[i]-i for i in range(len_arr)]\n",
    "        a2 = (max(ppp)-min(ppp))\n",
    "        ppp = [arr1[i]-arr2[i]+i for i in range(len_arr)]\n",
    "        a3 = (max(ppp)-min(ppp))\n",
    "        ppp = [arr1[i]-arr2[i]-i for i in range(len_arr)]\n",
    "        a4 = (max(ppp)-min(ppp))\n",
    "        return max(a1,a2,a3,a4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "inf=10**20\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n=len(arr1)\n",
    "        def f(arr):\n",
    "            res=-inf\n",
    "            mx=[arr[0],0]\n",
    "            mi=[arr[0],0]\n",
    "            for i in range(1,n):\n",
    "                res=max(res,arr[i]-mi[0]+i-mi[1],mx[0]-arr[i]+i-mx[1])\n",
    "                if (mx[0]-(-inf))+(i+1-mx[1])<(arr[i]-(-inf))+(i+1-i):\n",
    "                    mx=[arr[i],i]\n",
    "                if (inf-mi[0])+(i+1-mi[1])<(inf-arr[i])+(i+1-i):\n",
    "                    mi=[arr[i],i]\n",
    "            return res\n",
    "\n",
    "        arr=[x+y for x,y in zip(arr1,arr2)]\n",
    "        brr=[x-y for x,y in zip(arr1,arr2)]\n",
    "\n",
    "        return max(f(arr),f(brr))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "inf=10**20\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        n=len(arr1)\n",
    "        def f(arr):\n",
    "            res=-inf\n",
    "            mx=mi=arr[0]\n",
    "            mxidx=miidx=0\n",
    "            for i in range(1,n):\n",
    "                res=max(res,arr[i]-mi+i-miidx,mx-arr[i]+i-mxidx)\n",
    "                if (mx-(-inf))+(i+1-mxidx)<(arr[i]-(-inf))+(i+1-i):\n",
    "                    mx=arr[i]\n",
    "                    mxidx=i\n",
    "                if (inf-mi)+(i+1-miidx)<(inf-arr[i])+(i+1-i):\n",
    "                    mi=arr[i]\n",
    "                    miidx=i\n",
    "                #print(mi,miidx,mx,mxidx)\n",
    "            return res\n",
    "\n",
    "        arr=[x+y for x,y in zip(arr1,arr2)]\n",
    "        brr=[x-y for x,y in zip(arr1,arr2)]\n",
    "        #print(arr,brr)\n",
    "        return max(f(arr),f(brr))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        len_arr = len(arr1)\n",
    "        ppp = [arr1[i]+arr2[i]+i for i in range(len_arr)]\n",
    "        ppn = [arr1[i]+arr2[i]-i for i in range(len_arr)]\n",
    "        pnp = [arr1[i]-arr2[i]+i for i in range(len_arr)]\n",
    "        pnn = [arr1[i]-arr2[i]-i for i in range(len_arr)]\n",
    "        return max((max(ppp)-min(ppp)),(max(ppn)-min(ppn)),(max(pnp)-min(pnp)),(max(pnn)-min(pnn)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\r\n",
    "        n = len(arr1)\r\n",
    "        expressions = [\r\n",
    "            [arr1[i] + arr2[i] + i for i in range(n)],\r\n",
    "            [arr1[i] - arr2[i] + i for i in range(n)],\r\n",
    "            [arr1[i] + arr2[i] - i for i in range(n)],\r\n",
    "            [arr1[i] - arr2[i] - i for i in range(n)]\r\n",
    "        ]\r\n",
    "\r\n",
    "        ans = 0\r\n",
    "        for expr in expressions:\r\n",
    "            max_val = max(expr)\r\n",
    "            min_val = min(expr)\r\n",
    "            ans = max(ans, max_val - min_val)\r\n",
    "\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D = [], [], [], []\n",
    "        for i, (a, b) in enumerate(zip(arr1, arr2)):\n",
    "            A.append(a + b + i)\n",
    "            B.append(a + b - i)\n",
    "            C.append(a - b + i)\n",
    "            D.append(a - b - i)\n",
    "        \n",
    "        return max(max(A) - min(A), max(B) - min(B), max(C) - min(C), max(D) - min(D))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxAbsValExpr(self, arr1, arr2):\n",
    "        \"\"\"\n",
    "        :type arr1: List[int]\n",
    "        :type arr2: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        A, B, C, D= [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "            \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D= [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "            \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxAbsValExpr(self, arr1, arr2):\n",
    "        \"\"\"\n",
    "        :type arr1: List[int]\n",
    "        :type arr2: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        A, B, C, D= [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "            \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # 暴力解法，超时\r\n",
    "    def maxAbsValExpr0(self, arr1: List[int], arr2: List[int]) -> int:\r\n",
    "        res = 0\r\n",
    "        for i in range(len(arr1)):\r\n",
    "            for j in range(len(arr2)):\r\n",
    "                res = max(res, abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j))\r\n",
    "        return res\r\n",
    "\r\n",
    "    # 数学\r\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\r\n",
    "        A, B, C, D= [], [], [], []\r\n",
    "        for i in range(len(arr1)):\r\n",
    "            x, y = arr1[i], arr2[i]\r\n",
    "            A.append(x + y + i)\r\n",
    "            B.append(x + y - i)\r\n",
    "            C.append(x - y + i)\r\n",
    "            D.append(x - y - i)\r\n",
    "            \r\n",
    "        a = max(A) - min(A)\r\n",
    "        b = max(B) - min(B)\r\n",
    "        c = max(C) - min(C)\r\n",
    "        d = max(D) - min(D)        \r\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D = [], [], [], []\n",
    "        for i in range(0, len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x - y + i)\n",
    "            C.append(x - y - i)\n",
    "            D.append(x + y - i)\n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D= [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "            \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxAbsValExpr(self, arr1, arr2):\n",
    "        \"\"\"\n",
    "        :type arr1: List[int]\n",
    "        :type arr2: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        A, B, C, D= [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "            \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D= [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "            \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D = [], [], [], []  #分成4个子问题\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "\n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D = [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "        \n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)\n",
    "\n",
    "        return max(a, b, c, d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        # res = 0\n",
    "        # for i in range(len(arr1)-1):\n",
    "        #     for j in range(i+1, len(arr1)):\n",
    "        #         res = max(res, abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j))\n",
    "        # return res\n",
    "        A, B, C, D = [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)        \n",
    "        return max(a, b, c, d)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:\n",
    "        A, B, C, D = [], [], [], []\n",
    "        for i in range(len(arr1)):\n",
    "            x, y = arr1[i], arr2[i]\n",
    "            A.append(x + y + i)\n",
    "            B.append(x + y - i)\n",
    "            C.append(x - y + i)\n",
    "            D.append(x - y - i)\n",
    "        a = max(A) - min(A)\n",
    "        b = max(B) - min(B)\n",
    "        c = max(C) - min(C)\n",
    "        d = max(D) - min(D)\n",
    "        return max(a, b, c, d)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
